/**
 * 全排列2
 */
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
bool isOk(int R[], int k, int i)
{
    if (i > k)
    {
        for (int t = k; t < i; t++)
            if (R[t] == R[i])
                return false;
    }
    return true;
}
// 产生R[k:m]的全排列
void perm(int R[], int k, int m)
{
    // 完成一次搜索，找到一个合适的全排列
    if (k == m)
    {
        for (int i = 0; i < m; i++)
            cout << R[i];
        cout << endl;
    }
    for (int i = k; i < m; i++)
    {
        if (isOk(R, k, i))
        {
            swap(R[i], R[k]);
            perm(R, k + 1, m);
            swap(R[i], R[k]);
        }
    }
}

typedef struct BTNode
{
    int data;
    struct BTNode *lChild;
    struct BTNode *rChild;
} BTNode int s[100];
int top = -1;
void sumPath(BTNode *t, int sum)
{
    if (t)
    {
        s[++top] = t->data;
        if (t->lChild == NULL && t->rChild == NULL)
        {
            if (t->data == sum) // 符合条件，打印路径
            {
                for (int i = 0; i <= top; i++)
                    cout << s[i] <<” ”;
                cout << endl;
            }
        }
        sum -= T->data;
        pathsum(T - lChild, sum);
        pathsum(T - rChild, sum);
        top--; // 返回上一层
    }
}

/**
 * n皇后问题
 * 使用pos记录皇后出现的位置，下标为行号，元素值为列号。
 * 对于第一行，皇后可能出现在该行的任意一列。
 * 接下来递归地在剩余的n-1行中找n-1个皇后的位置。同时检查子问题是否符合条件
 */
bool Place(int pos[], int k)
{
    for (int j = 1; j < k; j++)
    {
        if ((abs(k - j)) == abs(pos[j] - pos[k]) ‖ (pos[j] == pos[k]))
            return false;
    }
    return true;
}
// 递归的搜索解空间树
void Backtrack(int pos[], int n, int t, int &sum)
{
    if (t > n)
        sum++;
    else
    {
        // 遍历所有列
        for (int i = 1; i <= n; i++)
        {
            pos[t] = i; // 满足要求，当前位置放置皇后
            if (Place(pos, t))
                Backtrack(pos, n, t + 1, sum); // 搜索下一行
        }
    }
}
// 计算n皇后的不同摆法数量
int nQueen(int n)
{
    int sum = 0;
    int *pos = new int[n + 1];
    Backtrack(pos, n, 1, sum);
    return sum;
}